/**
 * @file   undigraph.h
 * @author zhang-zh
 * @date   2020/1/2 Saturday
 * 
 * @brief  A headfile for undigraph without weight.
 * 
 */
#ifndef __zhang_undigraph__
#define __zhang_undigraph__

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

#define MAX (std::numeric_limits<int>::max())

using namespace std;

struct Edge
{
    int ori;   // The origin of the edge.
    int dest;  // The destination of the edge.
};

/**
 * Set a struct in order to get the shortest path.
 * 
 */
struct Node
{
    int distance;   // Record the distance.
    bool visited;   // As a mark. When a node is out of the
                    // queue, it won't be visited again.
};

class undigraph
{
public:
    vector< vector<int> > adjList;
    vector<Node> node;
    queue<int> myque;

    /**
     * Constructor.
     * 
     * @param edges All edges of a graph.
     * @param n The size of the list.
     */
    undigraph(vector<Edge> &edges, int n)
    {
        adjList.resize(n);
        for(auto &edge : edges)
        {
            int i = edge.ori;
            int j = edge.dest;
            adjList[i].push_back(j);
            adjList[j].push_back(i);
        }
        node.resize(n);
        for(int i = 0; i < n; i++)
        {
            node[i].distance = MAX;
            node[i].visited = true;
        }
    }

    /**
     * Get the length of the shortest path between
     * two points.
     * 
     * @param begin One of the points.
     * @param last The other one.
     * 
     * @return The length.
     */
    int shortestpath(int begin, int last)
    {
        int beg = begin;
        node[beg].distance = 0;
        myque.push(beg);
        while(!myque.empty())
        {
            auto v = myque.front();
            myque.pop();
            node[v].visited = false;
            for(auto c : adjList[v])
            {
                if(node[c].visited && node[c].distance == MAX)
                {
                    node[c].distance = node[v].distance + 1;
                    myque.push(c);
                }
            }
        }
        return node[last].distance;
    }
};

#endif